package chapter03_binaryTree.lowestAncestor;

import chapter03_binaryTree.Node;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 描述：
 *      找到两个结点最近的公共祖先
 *      进阶：如果查询两个结点公共祖先的操作非常频繁，想法让单条查询的查询时间变短
 *      再进阶：给定二叉树的头结点head，同时给定所有想要进行的查询，
 *              二叉树的结点个数为N，查询的条数为M，时间复杂度请达到O(N+M)
 *
 * @author hl
 * @date 2021/5/31 9:23
 */
public class LowestAncestor {
    public Node lowestAncestor(Node head, Node o1, Node o2){
        if (head == null || head == o1 || head == o2) {
            return head;
        }
        Node left = lowestAncestor(head.left, o1, o2);
        Node right = lowestAncestor(head.right, o1, o2);
        if (left != null && right != null) {
            //o1、o2向上的过程中首次相遇
            return head;
        }
        //不为空的那个结点，那么是o1、o2中的一个，要么是已经是o1、o2的公共祖先
        return left != null ? left : right;
    }

    Node ans = null;
    public Node lowestAncestor2(Node head, Node o1, Node o2){
        process(head, o1, o2);
        return ans;
    }

    private int process(Node head, Node o1, Node o2) {
        if (head == null) {
            return 0;
        }
        int lc = process(head.left, o1, o2);
        int rc = process(head.right, o1, o2);
        int count = lc + rc;
        if (count == 2 && ans == null) {
            ans = head;
        }
        if (head.val == o1.val || head.val == o2.val) {
            if (count == 1) {
                ans = head;
            }
            count++;
        }
        return count;
    }

    /**
     * 进阶问题
     * 方法一：建立一个hash表存储结点以及当前结点父节点之间的映射关系
     * 在查询时，首先查询出某个结点的祖先结点集合A，然后再自下而上查询另一个结点的父节点的集合，返回第一个集合A中存在的结点
     * 即最近的公共祖先
     *
     * 构建结构O(N)，查找O(h)，额外空间复杂度O(N)
     */
    public class Record1 {
        public HashMap<Node, Node> map;

        public Record1(Node head) {
            map = new HashMap<>();
            if (head != null) {
                map.put(head, null);
            }
            setMap(head);
        }

        private void setMap(Node head) {
            if (head != null) {
                if (head.left != null) {
                    map.put(head.left, head);
                }
                if (head.right != null) {
                    map.put(head.right, head);
                }
                setMap(head.left);
                setMap(head.right);
            }
        }
        public Node query(Node o1, Node o2){
            HashSet<Node> path = new HashSet<>();
            while(o1 != null){
                path.add(o1);
                o1 = map.get(o1);
            }
            while(!path.contains(o2)){
                o2 = map.get(o2);
            }
            return o2;
        }
    }

    /**
     * 进阶问题
     * 方法二：在初始化时构建一个结构存储整个二叉树每两个结点与他们之间的最近的公共祖先的映射关系，后面可以直接查询
     *
     * 重点在于如何构建起这个结构：
     *      1）二叉树的头结点是这个二叉树中任意结点与头结点的公共祖先
     *      2）二叉树的任意两个左右子树结点的公共祖先是这个二叉树的头结点
     */
    public class Record2{
        HashMap<Node, HashMap<Node, Node>> map;

        public Record2(Node head) {
            map = new HashMap<>();
            initMap(head);
            setMap(head);
        }

        /**
         * 将二叉树的每个结点作为key放入map中
         * @param head
         */
        private void initMap(Node head) {
            if (head == null) {
                return ;
            }
            map.put(head, new HashMap<>());
            initMap(head.left);
            initMap(head.right);
        }


        private void setMap(Node head) {
            if (head == null) {
                return ;
            }
            headRecord(head.left, head);
            headRecord(head.right, head);
            subRecord(head);
            setMap(head.left);
            setMap(head.right);
        }

        /**
         * 初始化以每个结点为key的映射关系
         * @param node
         * @param head
         */
        private void headRecord(Node node, Node head) {
            if (node == null) {
                return ;
            }
            map.get(node).put(head, head);
            headRecord(node.left, head);
            headRecord(node.right, head);
        }

        /**
         * head为头结点的左右子树中任意两个结点的最近公共祖先的是head， 存储三者的映射关系
         * @param head
         */
        private void subRecord(Node head) {
            if (head == null) {
                return ;
            }
            preLeft(head.left, head.right, head);
            //个人觉得这个递归没必要setMap中会进行递归
//            subRecord(head.left);
//            subRecord(head.right);
        }

        private void preLeft(Node l, Node r, Node head) {
            if (l == null) {
                return ;
            }
            preRight(l, r, head);
            preLeft(l.left, r, head);
            preLeft(l.right, r, head);
        }

        private void preRight(Node l, Node r, Node head) {
            if (r == null) {
                return ;
            }
            map.get(l).put(r, head);
            preRight(l, r.left, head);
            preRight(l, r.right, head);
        }

        public Node query(Node o1, Node o2){
            if (o1 == o2) {
                return o1;
            }
            if (map.containsKey(o1) && map.get(o1).containsKey(o2)) {
                return map.get(o1).get(o2);
            }
            if (map.containsKey(o2) && map.get(o2).containsKey(o1)) {
                return map.get(o2).get(o1);
            }
            return null;
        }

    }
}
